package sort

// QuickSort 快速排序
func QuickSort(arr []int) []int {
	// 选取mid
	midPtr := len(arr) >> 1
	// 递归结束条件
	if midPtr <= 0 {
		return arr
	}

	mid := arr[midPtr]

	// 找出左数组leftArr和右数组rightArr
	var leftArr, rightArr []int
	for i := 0; i < len(arr); i++ {
		if arr[i] <= mid && i != midPtr {
			leftArr = append(leftArr, arr[i])
		} else if arr[i] > mid && i != midPtr {
			rightArr = append(rightArr, arr[i])
		}
	}

	// 合并leftArr、mid、rightArr
	return merge(QuickSort(leftArr), mid, QuickSort(rightArr))
}

func merge(leftArr []int, mid int, rightArr []int) []int {
	res := append(leftArr, mid)
	res = append(res, rightArr...)
	return res
}
